\documentclass[11pt]{article}

\usepackage[top=3cm, bottom=3cm, left=3cm, right=3cm]{geometry}      % [top=2cm, bottom=2cm, left=2cm, right=2cm]
\geometry{letterpaper}                   % ... or a4paper or a5paper or ... 
%\geometry{landscape}                % Activate for for rotated page geometry
\usepackage[parfill]{parskip}    
\usepackage{graphicx}
\usepackage{amssymb, amsmath, amsthm, amsfonts}
\usepackage{enumerate}

\newcommand{\class}[1]{{\ensuremath{\mathsf{#1}}}}
\newcommand{\gen}{\class{Gen}}
\newcommand{\enc}{\class{Enc}}
\newcommand{\dec}{\class{Dec}}
\newcommand{\np}{\class{NP}}
\newcommand{\ip}{\class{IP}}
\newcommand{\zk}{\class{ZK}}
\newcommand{\pzk}{\class{PZK}}
\newcommand{\negl}{\class{negl}}
\newcommand{\poly}{\class{poly}}
\newcommand{\gni}{\class{GNI}}
\newcommand{\zo}{\{0, 1\}}
\newcommand{\vect}[1]{\textbf{#1}}
\newcommand{\zq}{\mathbb{Z}_q}
\newcommand{\cvect}[1]{(\vect{#1}_1, ... , \vect{#1}_k)}
\newcommand{\bL}{\bar{L}}
\newcommand{\Label}{\class{label}}
\newcommand{\ham}{\class{Ham}}


\newtheorem{definition}{Definition}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}

\begin{document}
\section{Interactive Proofs ($\ip$)}
\subsection{``classical" Proofs}
$\np$ is the class of languages $L$, s.t.
\begin{description}
\item[Completeness] If $x\in L$, then $\exists V$ s.t. $V(x, proof) = accept$. 
\item[Soundness] If $x\notin L$, then $\forall proof^*$, $V(x, proof^*) = reject$.
\item[Efficiency] $V(x, proof)$ runs in $\poly(|x|)$.
\end{description} 
\subsection{Interactive Proofs}
GMR generalize this concept Interactive Proof ($\ip$) to think of a proof as a game between a `proofer' and a `verifier'. The game can be interactive, where the verifier asks questions and the prover answers, and the goal of the game is for the prove to convince the verifier that the statement is true. The soundness is now probabilistic, i.e. the verifier may not get convinced ``only'' with high probability.


\begin{definition}
An interactive proof for the decision problem $\pi$, is a following process:
\begin{enumerate}
\item There are two participants, a prover and a verifier.
\item In the beginning of the proof both participants get the same input (representing the statement
to be proven).
\item The verifier and the prover exchange messages.
\item Both the verifier and the prover can perform some private computation and use local randomness.
\item At the end, the verifier states whether he was convinced or not.
\end{enumerate}
\end{definition}

\begin{definition}
An interactive proof for a language L with error $\nu$ is a two-party protocol $(P;V)$ such that:
\begin{enumerate}
\item (Efficiency) $V$ is a PPT.
\item (Completeness) If $x \in L$, then $Pr([P; V](1^n; x; 1^n; x) = (1; 1) > 1 - \nu$.
\item (Soundness) If $x \notin L$, then $Pr([P; V](1^n; x; 1^n; x) = (\bot; 1) < \nu$.
\end{enumerate}
Unless stated, otherwise we have $\nu$ in $\negl(|x|)$
\end{definition}

\begin{definition}
$\ip$ is the class of languages that have interactive proofs.
\end{definition}
\begin{definition}
$\ip = \class{PSPACE}$.
\end{definition}

\paragraph{Example}: $\class{GNI} \in \ip$.

Common input: graphs $G_0; G_1$:
\begin{enumerate}
\item $V$ chooses $b\in \zo$ randomly.
\item $V$ chooses a random permutation $\pi\in S_n$, where $n = |V|$ and computes a new graph $H = \pi(G_{b})$, and sends $H$ to $P$.
\item $P$ computes $b'$ such that $H$ is isomorphic to $G_{b'}$ $(H \approx G_{b'})$ and sends $b'$ to $V$ .
\item $V$ accepts if $b = b'$.
\end{enumerate}
Intuitively, a single run of $\Pi_\gni$ gives a soundness error at most 1/2. Let's run $\Pi_\gni$ instance $k$ times, denote $\Pi_\gni^k$, then $\Pi_\gni^k$ has the soundness error $\frac{1}{2^k}$



\section{Zero Knowledge ($\zk$)}
\begin{definition}[\textbf{first attempt to define $\zk$}]
A proof system for a language L is an
$\ip$ $(V_L; P_L)$ for $L$, such that there is a probabilistic algorithm $S$ (or ``Simulator") that
runs in expected polynomial time and such that for every string $x\in L$ the distribution of outputs of
$S(x)$ is identical to the distribution of views of $V_L$ of the interaction between $P_L$ and $V_L$ on input $x$.
\end{definition}
$\forall x \in L$, $VIEW^{(A;S)}_A(a; b; 1^n) = VIEW^{(A;P_L)}_A (a; b; 1^n)$.

The definition will holds for every verifier follows the protocol's rules, however, it is not strong enough since a cheating verifier may gain some information by not following the protocol.

\begin{definition}[\textbf{Perfect $\zk$}]
A proof system for a language L is an $\ip$ $(V_L; P_L)$ for $L$, such that for every polynomial time verifier $V^*$, $\exists$ a probabilistic algorithm $S$ (for Simulator) that runs in average polynomial time and such that for every string $x \in L$ the distribution of outputs of $S(x)$ is identical to the distribution of views of $V^*$ of the interaction between $P_L$ and $V^*$ on input x.
\end{definition}
This stronger condition implies that the prover can still deliver a convincing proof that $x \in L$ without giving away any information about $x$, even if the prover does not trust the verifier to follow the protocol of the proof system.

Consider the following protocol for $GI$, which we denote $\Pi_{GI}$.

Common input: graphs $G_0, G_1$.
\begin{enumerate}
\item $P$ chooses a random permutation $\sigma$.
\item $P$ computes $H = \sigma(G_0)$ and send $H$ to $V$.
\item $V$ chooses a random bit $b \leftarrow \zo$ and send it to $P$.
\item $P$ computes $H = \rho(G_b)$, where $\rho = \sigma$ if $b=0$, o/w $\rho = \sigma \cdot \pi$.

Then send $\rho$ to $V$.
\item $V$ accepts if $H = \rho(G_b)$.
\end{enumerate}
\begin{lemma}
The  protocol $\Pi_{GI}$ is in 	$\pzk$.
\end{lemma}

\section{Sequential composition of ZK}
If the simulator cannot also get some prior knowledge, then it may not be able to simulate the same conversations. Therefore, we might allow a more powerful simulator to have this prior knowledge, sometimes referred to as an ``advice string", ``auxiliary input", or simply $z$.
\begin{definition} \textbf{An interactive proof (P,V) with auxiliary input is Zero Knowledge} if for any polynomial time algorithm $V^*$ there exists a polynomial simulator $S$ such that, for any input $x \in L$ and for any $z$.
$$S(x, z) = [P, V^*](x, (x, z)) $$
\end{definition}
\begin{theorem}
Let $(P, V)$ be an auxiliary-input ZK two-party protocol with $\poly.$ V , and let $(P^k , V^k)$ be the protocol that runs $(P, V)$ sequentially $k$ times (on the same common input). Then $(P^k , V^k )$ is auxiliary input ZK.
\end{theorem}

\textbf{Proof Sketch: }Consider some ``cheating verifier'' $V^{k*}$ . To construct a simulator $S^*$ for $V^{k*}$ , we first define a ``cheating verifier'' $V^*$ for the original protocol $(P, V )$: $V^*$ treats its auxiliary input $z$ as a state for $V^{k*}$ . It then runs $V^{k*}$ from state $z$, for a single interaction with the prover. $V^*$ then outputs the current internal state of the $V^{k*}$.

By definition, $V^*$ has a simulator $S$. We now construct $S^k$ from $S$: $S^k$ simply runs $S$, $k$ times, where the first run starts with the auxiliary input of $S^k$, and for $i > 1$ the $i$-th run starts with auxiliary input which is the output of the $(i-1)$ run of $S$.

\paragraph{Blum Protocol for Hamiltonian cycle problem: }
\begin{itemize}
\item Public input: $x = (x_{i,j})$, the adjacency matrix of an undirected graph on $n$ vertices.
\item Prover’s auxiliary input: $w$, a hamiltonian cycle in the graph $x$.
\end{itemize}
\textbf{Protocol:}
\begin{description}
\item[Step 1 (Commitment to permuted graph):] Prover selects a random permutation $\varphi$ on the vertices, and computes a commitment to the permuted graph, i.e. prover sends the matrix of commitments $C = (C_{i,j})$ where $C_{i,j} = \class{Comm}(x_{\varphi(i),\varphi(j)})$.
\item[Step V2 (Send random query):] The verifier selects a random bit $b \leftarrow_R \zo$ and sends it.
\item[Step P3 (Open commitments):] If $b = 0$ then the prover sends decommitments for all the commitments sent in Step P1 and in addition sends the permutation $\varphi$ chosen in that step. Otherwise (if $b = 1$) the prover sends decommitments only for the commitments that correspond to the edges of $\varphi(w)$. (i.e., the edges of the permuted Hamiltonian cycle).
\end{description}
\textbf{Note: }1). If $b = 0$ then the verifier accepts iff all decommitments are valid and form a graph $x'$ such that $x' = \varphi(x)$ (i.e., $x'_{i,j} = x_{\varphi(i),\varphi(j)}$ for all $i, j \in [n]$). \\
2).If $b = 1$ then the verifier accepts iff the decommitments sent are for a Hamiltonian cycle and all the opened commitments are to the value 1.

\paragraph{3-colorability:} 
A coloring of a graph G can be viewed as function $\phi$ from the vertices of $G$ to the set, say $\{r, g, b\}$, such that if $(u, v)$ is an edge in $G$, then $\phi(u)= \phi(v)$. The decision versions of the 3-coloring problem is a $\np$-Complete problem.

We now show a $\zk$ proof for 3-colorability: \\
\textbf{Input of the protocol: } Graph $G$ with $n$ vertices.\\
\textbf{Prove's proof: } Prover knows a coloring function $\phi$ in $G$.
\begin{itemize}
\item First, the prover chooses a random permutation $\varphi$ over the set $\{r, g, b\}$. He then commits to the (permuted) coloring vertex-by-vertex, and sends the $n$ many commitments $\class{Comm}(\varphi(\phi_1)), ..., \class{Comm}(\varphi(\phi_n))$.
\item The verifier chooses a random edge $(i, j)$ in G, and sends $(i, j)$ to the prover.
\item The prover sends decommitments to the $i$th and $j$th commitments that it sent in the first round.
\item The verifier recovers the decommitted values, denoted $\varphi_i$ and $\varphi_j$. The verifier accepts iff $\varphi_i, \varphi_j \in \{r, g, b\}$ with $\varphi_i \ne \varphi_j$.
\end{itemize}
A cheating prover fails to convince the verifier with probability at least $1/n^2$, which is inverse polynomial. Since the graph is not 3-colorable, there must then be at least one edge $(u, v)$ for which $u$ and $v$ are assigned the same color. So if the verifier chooses this edge, he will reject the proof. The probability that the verifier chooses such an edge is (at least) $1/|E| \le 1/n^2$.

As usual, repeating the protocol sufficiently many (but polynomially-many) times (sequentially if we want to preserve the ZK property) yields a proof system with negligible soundness error.
\end{document}













